combinatorial Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...

mathematics, a de Bruijn sequence of order ''n'' on a size-''k''

alphabet An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syllab ...

''A'' is a cyclic sequence in which every possible length-''n'' string on ''A'' occurs exactly once as a

substring In formal language theory and computer science, a substring is a contiguous sequence of characters within a string. For instance, "''the best of''" is a substring of "''It was the best of times''". In contrast, "''Itwastimes''" is a subsequenc ...

(i.e., as a ''contiguous''

subsequence In mathematics, a subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. For example, the sequence \langle A,B,D \rangle is a ...

). Such a sequence is denoted by and has length , which is also the number of distinct strings of length ''n'' on ''A''. Each of these distinct strings, when taken as a substring of , must start at a different position, because substrings starting at the same position are not distinct. Therefore, must have ''at least'' symbols. And since has ''exactly'' symbols, De Bruijn sequences are optimally short with respect to the property of containing every string of length ''n'' at least once. The number of distinct de Bruijn sequences is :

\dfrac.

The sequences are named after the Dutch mathematician

Nicolaas Govert de Bruijn Nicolaas Govert (Dick) de Bruijn (; 9 July 1918 – 17 February 2012) was a Dutch mathematician, noted for his many contributions in the fields of analysis, number theory, combinatorics and logic.

, who wrote about them in 1946. As he later wrote, the existence of de Bruijn sequences for each order together with the above properties were first proved, for the case of alphabets with two elements, by . The generalization to larger alphabets is due to .

Automata An automaton (; plural: automata or automatons) is a relatively self-operating machine, or control mechanism designed to automatically follow a sequence of operations, or respond to predetermined instructions.Automaton – Definition and More ...

for recognizing these sequences are denoted as de Bruijn automata. In most applications, ''A'' = .

History

The earliest known example of a de Bruijn sequence comes from

Sanskrit prosody Sanskrit prosody or Chandas refers to one of the six Vedangas, or limbs of Vedic studies.James Lochtefeld (2002), "Chandas" in The Illustrated Encyclopedia of Hinduism, Vol. 1: A-M, Rosen Publishing, , page 140 It is the study of poetic met ...

where, since the work of

Pingala Acharya Pingala ('; c. 3rd2nd century BCE) was an ancient Indian poet and mathematician, and the author of the ' (also called the ''Pingala-sutras''), the earliest known treatise on Sanskrit prosody. The ' is a work of eight chapters in the la ...

, each possible three-syllable pattern of long and short syllables is given a name, such as 'y' for short–long–long and 'm' for long–long–long. To remember these names, the mnemonic ''yamātārājabhānasalagām'' is used, in which each three-syllable pattern occurs starting at its name: 'yamātā' has a short–long–long pattern, 'mātārā' has a long–long–long pattern, and so on, until 'salagām' which has a short–short–long pattern. This mnemonic, equivalent to a de Bruijn sequence on binary 3-tuples, is of unknown antiquity, but is at least as old as Charles Philip Brown's 1869 book on Sanskrit prosody that mentions it and considers it "an ancient line, written by

Pāṇini , era = ;;6th–5th century BCE , region = Indian philosophy , main_interests = Grammar, linguistics , notable_works = ' ( Classical Sanskrit) , influenced= , notable_ideas=Descriptive linguistics (Devanaga ...

". In 1894, A. de Rivière raised the question in an issue of the French problem journal '' L'Intermédiaire des Mathématiciens'', of the existence of a circular arrangement of zeroes and ones of size

2^n

that contains all

2^n

binary sequences of length

n

. The problem was solved (in the affirmative), along with the count of

2^

distinct solutions, by Camille Flye Sainte-Marie in the same year. This was largely forgotten, and proved the existence of such cycles for general alphabet size in place of 2, with an algorithm for constructing them. Finally, when in 1944 Kees Posthumus conjectured the count

2^

for binary sequences, de Bruijn proved the conjecture in 1946, through which the problem became well-known. Karl Popper independently describes these objects in his ''

The Logic of Scientific Discovery ''The Logic of Scientific Discovery'' is a 1959 book about the philosophy of science by the philosopher Karl Popper. Popper rewrote his book in English from the 1934 (imprint '1935') German original, titled ''Logik der Forschung. Zur Erkenntnisthe ...

'' (1934), calling them "shortest random-like sequences".

Examples

* Taking ''A'' = , there are two distinct ''B''(2, 3): 00010111 and 11101000, one being the reverse or negation of the other. * Two of the 16 possible ''B''(2, 4) in the same alphabet are 0000100110101111 and 0000111101100101. * Two of the 2048 possible ''B''(2, 5) in the same alphabet are 00000100011001010011101011011111 and 00000101001000111110111001101011.

Construction

De bruijn graph-for binary sequence of order 4

The de Bruijn sequences can be constructed by taking a

Hamiltonian path In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

of an ''n''-dimensional

de Bruijn graph In graph theory, an -dimensional De Bruijn graph of symbols is a directed graph representing overlaps between sequences of symbols. It has vertices, consisting of all possible sequences of the given symbols; the same symbol may appear multiple ...

over ''k'' symbols (or equivalently, an

Eulerian cycle In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends ...

of an (''n'' − 1)-dimensional de Bruijn graph). An alternative construction involves concatenating together, in lexicographic order, all the

Lyndon word In mathematics, in the areas of combinatorics and computer science, a Lyndon word is a nonempty string that is strictly smaller in lexicographic order than all of its rotations. Lyndon words are named after mathematician Roger Lyndon, who in ...

s whose length divides ''n''. An inverse

Burrows–Wheeler transform The Burrows–Wheeler transform (BWT, also called block-sorting compression) rearranges a character string into runs of similar characters. This is useful for compression, since it tends to be easy to compress a string that has runs of repeated c ...

can be used to generate the required Lyndon words in lexicographic order. De Bruijn sequences can also be constructed using

shift register A shift register is a type of digital circuit using a cascade of flip-flops where the output of one flip-flop is connected to the input of the next. They share a single clock signal, which causes the data stored in the system to shift from one loc ...

s or via

finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...

Example using de Bruijn graph

Goal: to construct a ''B''(2, 4) de Bruijn sequence of length 2⁴ = 16 using Eulerian (''n'' − 1 = 4 − 1 = 3) 3-D de Bruijn graph cycle. Each edge in this 3-dimensional de Bruijn graph corresponds to a sequence of four digits: the three digits that label the vertex that the edge is leaving followed by the one that labels the edge. If one traverses the edge labeled 1 from 000, one arrives at 001, thereby indicating the presence of the subsequence 0001 in the de Bruijn sequence. To traverse each edge exactly once is to use each of the 16 four-digit sequences exactly once. For example, suppose we follow the following Eulerian path through these vertices: :000, 000, 001, 011, 111, 111, 110, 101, 011, ::110, 100, 001, 010, 101, 010, 100, 000. These are the output sequences of length ''k'': :0 0 0 0 :_ 0 0 0 1 :_ _ 0 0 1 1 This corresponds to the following de Bruijn sequence: :0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 The eight vertices appear in the sequence in the following way: 1 1 1 1 0 1 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 1 1 1 0 0 1 0 1 0 0 0 0 1 1 1 0 0 1 0 1 0 0 0 0 1 1 1 0 0 1 0 1 0 0 0 0 1 1 1 1 0 1 0 1 0 0 0 0 1 1 1 1 0 1 0 1 0 0 0 0 1 1 1 1 0 1 0 1 0 0 0 0 1 1 1 1 0 1 1 1 0 0 0 0 1 1 1 1 0 1 1 0 0} 0 0 0 1 1 1 1 0 1 1 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 1 1 1 0 1 1 0 0 1 0 {1 ... ...and then we return to the starting point. Each of the eight 3-digit sequences (corresponding to the eight vertices) appears exactly twice, and each of the sixteen 4-digit sequences (corresponding to the 16 edges) appears exactly once.

Example using inverse Burrows—Wheeler transform

Mathematically, an inverse Burrows—Wheeler transform on a word generates a multi-set of equivalence classes consisting of strings and their rotations. These equivalence classes of strings each contain a

as a unique minimum element, so the inverse Burrows—Wheeler transform can be considered to generate a set of Lyndon words. It can be shown that if we perform the inverse Burrows—Wheeler transform on a word consisting of the size-''k'' alphabet repeated ''k''^''n''−1 times (so that it will produce a word the same length as the desired de Bruijn sequence), then the result will be the set of all Lyndon words whose length divides ''n''. It follows that arranging these Lyndon words in lexicographic order will yield a de Bruijn sequence ''B''(''k'',''n''), and that this will be the first de Bruijn sequence in lexicographic order. The following method can be used to perform the inverse Burrows—Wheeler transform, using its ''standard permutation'': # Sort the characters in the string , yielding a new string # Position the string above the string , and map each letter's position in to its position in while preserving order. This process defines th
Standard Permutation
# Write this permutation in

cycle notation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or p ...

with the smallest position in each cycle first, and the cycles sorted in increasing order. # For each cycle, replace each number with the corresponding letter from string in that position. # Each cycle has now become a Lyndon word, and they are arranged in lexicographic order, so dropping the parentheses yields the first de Bruijn sequence. For example, to construct the smallest ''B''(2,4) de Bruijn sequence of length 2⁴ = 16, repeat the alphabet (ab) 8 times yielding . Sort the characters in , yielding . Position above as shown, and map each element in to the corresponding element in by drawing a line. Number the columns as shown so we can read the cycles of the permutation: BurrowsWheeler- standard permutation

Starting from the left, the Standard Permutation notation cycles are: .
Standard Permutation
Then, replacing each number by the corresponding letter in from that column yields: . These are all of the Lyndon words whose length divides 4, in lexicographic order, so dropping the parentheses gives .

Algorithm

The following

Python Python may refer to: Snakes * Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia ** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia * Python (mythology), a mythical serpent Computing * Python (pro ...

code calculates a de Bruijn sequence, given ''k'' and ''n'', based on an algorithm from

Frank Ruskey Frank Ruskey is a combinatorialist and computer scientist, and professor at the University of Victoria. His research involves algorithms for exhaustively listing discrete structures, combinatorial Gray codes, Venn and Euler diagrams, combinato ...

's ''Combinatorial Generation''. from typing import Iterable, Union, Any def de_bruijn(k: Union terable[Any_int.html" ;"title="ny.html" ;"title="terable[Any">terable[Any int">ny.html" ;"title="terable[Any">terable[Any int n: int) -> str: """de Bruijn sequence for alphabet k and subsequences of length n. """ # Two kinds of alphabet input: an integer expands # to a list of integers as the alphabet.. if isinstance(k, int): alphabet = list(map(str, range(k))) else: # While any sort of list becomes used as it is alphabet = k k = len(k) a = [0] * k * n sequence = [] def db(t, p): if t > n: if n % p

0: sequence.extend(a[1 : p + 1]) else: a = a[t - p] db(t + 1, p) for j in range(a - p+ 1, k): a = j db(t + 1, t) db(1, 1) return "".join(alphabet for i in sequence) print(de_bruijn(2, 3)) print(de_bruijn("abcd", 2)) which prints 00010111 aabacadbbcbdccdd Note that these sequences are understood to "wrap around" in a cycle. For example, the first sequence contains 110 and 100 in this fashion.

Uses

De Bruijn cycles are of general use in neuroscience and psychology experiments that examine the effect of stimulus order upon neural systems, and can be specially crafted for use with functional magnetic resonance imaging.

Angle detection

The symbols of a de Bruijn sequence written around a circular object (such as a wheel of a

robot A robot is a machine—especially one programmable by a computer—capable of carrying out a complex series of actions automatically. A robot can be guided by an external control device, or the control may be embedded within. Robots may ...

) can be used to identify its

angle In Euclidean geometry, an angle is the figure formed by two rays, called the '' sides'' of the angle, sharing a common endpoint, called the '' vertex'' of the angle. Angles formed by two rays lie in the plane that contains the rays. Angles a ...

by examining the ''n'' consecutive symbols facing a fixed point. This angle-encoding problem is known as the "rotating drum problem". Gray codes can be used as similar rotary positional encoding mechanisms, a method commonly found in

rotary encoder A rotary encoder, also called a shaft encoder, is an electro-mechanical device that converts the angular position or motion of a shaft or axle to analog or digital output signals. There are two main types of rotary encoder: absolute and increm ...

Finding least- or most-significant set bit in a word

A de Bruijn sequence can be used to quickly find the index of the least significant set bit ("right-most 1") or the most significant set bit ("left-most 1") in a

word A word is a basic element of language that carries an objective or practical meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of what a word is, there is no conse ...

using bitwise operations and multiplication. The following example uses a de Bruijn sequence to determine the index of the least significant set bit (equivalent to counting the number of trailing '0' bits) in a 32 bit unsigned integer: uint8_t lowestBitIndex(uint32_t v) { static const uint8_t BitPositionLookup 2= // hash table { 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 }; return BitPositionLookup (uint32_t)((v & -v) * 0x077CB531U)) >> 27 } The lowestBitIndex() function returns the index of the least-significant set bit in ''v'', or zero if ''v'' has no set bits. The constant 0x077CB531U in the expression is the ''B'' (2, 5) sequence 0000 0111 0111 1100 1011 0101 0011 0001 (spaces added for clarity). The operation (v & -v) zeros all bits except the least-significant bit set, resulting in a new value which is a power of 2. This power of 2 is multiplied (arithmetic modulo 2³²) by the de Bruijn sequence, thus producing a 32-bit product in which the bit sequence of the 5 MSBs is unique for each power of 2. The 5 MSBs are shifted into the LSB positions to produce a hash code in the range

, 31 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline o ...

which is then used as an index into

hash table In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', ...

BitPositionLookup. The selected hash table value is the bit index of the least significant set bit in ''v''. The following example determines the index of the most significant bit set in a 32 bit unsigned integer: uint32_t keepHighestBit(uint32_t n) { n , = (n >> 1); n , = (n >> 2); n , = (n >> 4); n , = (n >> 8); n , = (n >> 16); return n - (n >> 1); } uint8_t highestBitIndex(uint32_t v) { static const uint8_t BitPositionLookup 2= { // hash table 0, 1, 16, 2, 29, 17, 3, 22, 30, 20, 18, 11, 13, 4, 7, 23, 31, 15, 28, 21, 19, 10, 12, 6, 14, 27, 9, 5, 26, 8, 25, 24, }; return BitPositionLookup keepHighestBit(v) * 0x06EB14F9U) >> 27 } In the above example an alternative de Bruijn sequence (0x06EB14F9U) is used, with corresponding reordering of array values. The choice of this particular de Bruijn sequence is arbitrary, but the hash table values must be ordered to match the chosen de Bruijn sequence. The keepHighestBit() function zeros all bits except the most-significant set bit, resulting in a value which is a power of 2, which is then processed as in the previous example.

Brute-force attacks on locks

{, class="infobox wikitable collapsible collapsed" style="text-align:center;font-size:80%;line-height:0.5;" , - style="text-align:left;font-size:125%;line-height:1;" , colspan="10", B{10,3} with digits read from top to bottom
then left to right; appending "00" yields
a string to brute-force a 3-digit combination lock , - style="vertical-align:top;" , 0 , rowspan="12", 1 , rowspan="23", 2 , rowspan="34", 3 , rowspan="45", 4 , rowspan="56", 5 , rowspan="67", 6 , rowspan="78", 7 , rowspan="89", 8 , rowspan="99", 9 , - , 001 , - , 002 , - , 003 , - , 004 , - , 005 , - , 006 , - , 007 , - , 008 , - , 009 , - , , - , 011 , - , 012, , 112 , - , 013, , 113 , - , 014, , 114 , - , 015, , 115 , - , 016, , 116 , - , 017, , 117 , - , 018, , 118 , - , 019, , 119 , - , , - , 021 , - , 022, , 122 , - , 023, , 123, , 223 , - , 024, , 124, , 224 , - , 025, , 125, , 225 , - , 026, , 126, , 226 , - , 027, , 127, , 227 , - , 028, , 128, , 228 , - , 029, , 129, , 229 , - , , , rowspan="2", , - , 031 , - , 032, , 132 , - , 033, , 133, , 233 , - , 034, , 134, , 234, , 334 , - , 035, , 135, , 235, , 335 , - , 036, , 136, , 236, , 336 , - , 037, , 137, , 237, , 337 , - , 038, , 138, , 238, , 338 , - , 039, , 139, , 239, , 339 , - , , , rowspan="2", , , rowspan="3", , - , 041 , - , 042, , 142 , - , 043, , 143, , 243 , - , 044, , 144, , 244, , 344 , - , 045, , 145, , 245, , 345, , 445 , - , 046, , 146, , 246, , 346, , 446 , - , 047, , 147, , 247, , 347, , 447 , - , 048, , 148, , 248, , 348, , 448 , - , 049, , 149, , 249, , 349, , 449 , - , , , rowspan="2", , , rowspan="3", , , rowspan="4", , - , 051 , - , 052, , 152 , - , 053, , 153, , 253 , - , 054, , 154, , 254, , 354 , - , 055, , 155, , 255, , 355, , 455 , - , 056, , 156, , 256, , 356, , 456, , 556 , - , 057, , 157, , 257, , 357, , 457, , 557 , - , 058, , 158, , 258, , 358, , 458, , 558 , - , 059, , 159, , 259, , 359, , 459, , 559 , - , , , rowspan="2", , , rowspan="3", , , rowspan="4", , , rowspan="5", , - , 061 , - , 062, , 162 , - , 063, , 163, , 263 , - , 064, , 164, , 264, , 364 , - , 065, , 165, , 265, , 365, , 465 , - , 066, , 166, , 266, , 366, , 466, , 566 , - , 067, , 167, , 267, , 367, , 467, , 567, , 667 , - , 068, , 168, , 268, , 368, , 468, , 568, , 668 , - , 069, , 169, , 269, , 369, , 469, , 569, , 669 , - , , , rowspan="2", , , rowspan="3", , , rowspan="4", , , rowspan="5", , , rowspan="6", , - , 071 , - , 072, , 172 , - , 073, , 173, , 273 , - , 074, , 174, , 274, , 374 , - , 075, , 175, , 275, , 375, , 475 , - , 076, , 176, , 276, , 376, , 476, , 576 , - , 077, , 177, , 277, , 377, , 477, , 577, , 677 , - , 078, , 178, , 278, , 378, , 478, , 578, , 678, , 778 , - , 079, , 179, , 279, , 379, , 479, , 579, , 679, , 779 , - , , , rowspan="2", , , rowspan="3", , , rowspan="4", , , rowspan="5", , , rowspan="6", , , rowspan="7", , - , 081 , - , 082, , 182 , - , 083, , 183, , 283 , - , 084, , 184, , 284, , 384 , - , 085, , 185, , 285, , 385, , 485 , - , 086, , 186, , 286, , 386, , 486, , 586 , - , 087, , 187, , 287, , 387, , 487, , 587, , 687 , - , 088, , 188, , 288, , 388, , 488, , 588, , 688, , 788 , - , 089, , 189, , 289, , 389, , 489, , 589, , 689, , 789, , 889 , - , , , rowspan="2", , , rowspan="3", , , rowspan="4", , , rowspan="5", , , rowspan="6", , , rowspan="7", , , rowspan="8", , - , 091 , - , 092, , 192 , - , 093, , 193, , 293 , - , 094, , 194, , 294, , 394 , - , 095, , 195, , 295, , 395, , 495 , - , 096, , 196, , 296, , 396, , 496, , 596 , - , 097, , 197, , 297, , 397, , 497, , 597, , 697 , - , 098, , 198, , 298, , 398, , 498, , 598, , 698, , 798 , - , 099, , 199, , 299, , 399, , 499, , 599, , 699, , 799, , 899, , (00) A de Bruijn sequence can be used to shorten a brute-force attack on a

PIN A pin is a device used for fastening objects or material together. Pin or PIN may also refer to: Computers and technology * Personal identification number (PIN), to access a secured system ** PIN pad, a PIN entry device * PIN, a former Dutch ...

-like code lock that does not have an "enter" key and accepts the last ''n'' digits entered. For example, a

digital door lock An electronic lock (or electric lock) is a locking device which operates by means of electric current. Electric locks are sometimes stand-alone with an electronic control assembly mounted directly to the lock. Electric locks may be connected to ...

with a 4-digit code (each digit having 10 possibilities, from 0 to 9) would have ''B'' (10, 4) solutions, with length . Therefore, only at most (as the solutions are cyclic) presses are needed to open the lock, whereas trying all codes separately would require presses.

f-fold de Bruijn sequences

''f-fold n-ary de Bruijn sequence is an extension of the notion ''n''-ary de Bruijn sequence, such that the sequence of the length

fk^n

contains every possible

of the length ''n'' exactly ''f'' times. For example, for

n=2

the cyclic sequences 11100010 and 11101000 are two-fold binary de Bruijn sequences. The number of two-fold de Bruijn sequences,

N_n

for

n=1

N_1=2

, the other known numbers are

N_2=5

N_3=72

, and

N_4=43768

De Bruijn torus

de Bruijn torus In combinatorial mathematics, a De Bruijn torus, named after Dutch mathematician Nicolaas Govert de Bruijn, is an array of symbols from an alphabet (often just 0 and 1) that contains every possible matrix of given dimensions exactly once. It is ...

is a toroidal array with the property that every ''k''-ary ''m''-by-''n'' matrix occurs exactly once. Such a pattern can be used for two-dimensional positional encoding in a fashion analogous to that described above for rotary encoding. Position can be determined by examining the ''m''-by-''n'' matrix directly adjacent to the sensor, and calculating its position on the de Bruijn torus.

De Bruijn decoding

Computing the position of a particular unique tuple or matrix in a de Bruijn sequence or torus is known as the de Bruijn Decoding Problem. Efficient decoding algorithms exist for special, recursively constructed sequences and extend to the two dimensional case. De Bruijn decoding is of interest, e.g., in cases where large sequences or tori are used for positional encoding.

Notes

References

* * * * * * * * * * * * * * * * * * * * * * Reprinted in Wardhaugh, Benjamin, ed. (2012), ''A Wealth of Numbers: An Anthology of 500 Years of Popular Mathematics Writing'',

Princeton University Press Princeton University Press is an independent publisher with close connections to Princeton University. Its mission is to disseminate scholarship within academia and society at large. The press was founded by Whitney Darrow, with the financia ...

, pp. 139–144. * *

External links

* *
De Bruijn sequence

CGI generator

Javascript generator and decoder
Implementation of J. Tuliani's algorithm.

* http://debruijnsequence.org has many kinds of de Bruijn sequences. {{DEFAULTSORT:Bruijn sequence, de Binary sequences Enumerative combinatorics Articles with example Python (programming language) code